package com.origin.niuke.simulation;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/15 17:28
 * 表达式求值
 * 请写一个整数计算器，支持加减乘三种运算和括号。
 * 算法：模拟 + 栈
 */
public class NC137 {
    public static void main(String[] args) {
        System.out.println(new NC137().solve("2*-1"));
    }
    // 定义运算符优先级
    static final Map<Character, Integer> MAP = new HashMap<>();
    static {
        MAP.put('-', 1);
        MAP.put('+', 1);
        MAP.put('*', 2);
    }

    public int solve(String s) {
        s = s.replaceAll(" ", "");
        char[] array = s.toCharArray();
        int n = array.length;
        // 存放数字
        Deque<Integer> nums = new ArrayDeque<>();
        // 防止开头是负数, 比如 -1, 加入 0 后, 就变成了 0 - 1
        nums.addLast(0);
        // 存放所有非数字
        Deque<Character> ops = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (array[i] == '(') ops.addLast('(');
            else if (array[i] == ')') {
                // 计算到最近一个左括号为止
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') calc(nums, ops);
                    else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNumber(array[i])) {
                    int tmp = 0, j = i;
                    while (j < n && isNumber(array[j])) tmp = tmp * 10 + (array[j++] - '0');
                    i = j - 1;
                    nums.addLast(tmp);
                } else {
                    // array[i] 为运算符号, 1*(-1) ==> 1*(0-1)
                    if (i > 0 && array[i - 1] == '(') nums.addLast(0);
                    // 有一个新操作符入栈时, 先把栈内能算的都算了
                    //只有满足栈内的运算符优先级比当前运算符优先级才能算
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (MAP.get(prev) >= MAP.get(array[i])) calc(nums, ops);
                        else break;
                    }
                    ops.addLast(array[i]);
                }
            }
        }
        // 将剩余的计算完
        while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
        return nums.peekLast();
    }

    void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        int ans = 0;
        if (op == '+') ans = a + b;
        else if (op == '-') ans = a - b;
        else if (op == '*') ans = a * b;
        nums.addLast(ans);
    }

    boolean isNumber(char c) {
        return Character.isDigit(c);
    }

}
